/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package me.magicall.util.comparator;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Comparator;
import java.util.List;

/**
 * <p>
 * A ComparatorChain is a Comparator that wraps one or more Comparators in sequence. The ComparatorChain calls each Comparator in sequence until either 1) any single Comparator returns a non-zero result (and that result is then returned), or 2) the ComparatorChain is exhausted (and zero is
 * returned). This type of sorting is very similar to multi-column sorting in SQL, and this class allows Java classes to emulate that kind of behaviour when sorting a List.
 * </p>
 * <p>
 * To further facilitate SQL-like sorting, the order of any single Comparator in the list can be reversed.
 * </p>
 * <p>
 * Calling a method that adds new Comparators or changes the ascend/descend sort <i>after compare(Object, Object) has been called</i> will result in an UnsupportedOperationException. However, <i>take care</i> to not alter the underlying List of Comparators or the BitSet that defines the sort order.
 * </p>
 * <p>
 * Instances of ComparatorChain are not synchronized. The class is not thread-safe at construction time, but it <i>is</i> thread-safe to perform multiple comparisons after all the setup operations are complete.
 * </p>
 * 
 * @since Commons Collections 2.0
 * @author Morgan Delagrange
 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10
 * Apr 2008) $
 */
public class ComparatorChain<T> implements Comparator<T>, Serializable {

	/** Serialization version from Collections 2.0. */
	private static final long serialVersionUID = -721644942746081630L;

	/** The list of comparators in the chain. */
	protected List<Comparator<? super T>> chain = null;
	/** Order - false (clear) = ascend; true (set) = descend. */
	protected BitSet orderingBits = null;
	/** Whether the chain has been "locked". */
	protected boolean isLocked = false;

	//-----------------------------------------------------------------------
	/**
	 * Construct a ComparatorChain with no Comparators. You must add at
	 * least one Comparator before calling the compare(Object,Object)
	 * method, or an UnsupportedOperationException is thrown
	 */
	public ComparatorChain() {
		this(new ArrayList<Comparator<? super T>>(), new BitSet());
	}

	/**
	 * Construct a ComparatorChain with a single Comparator, sorting in the
	 * forward order
	 * 
	 * @param comparator First comparator in the Comparator chain
	 */
	public ComparatorChain(Comparator<? super T> comparator) {
		this(comparator, false);
	}

	/**
	 * Construct a Comparator chain with a single Comparator, sorting in
	 * the given order
	 * 
	 * @param comparator First Comparator in the ComparatorChain
	 * @param reverse false = forward sort; true = reverse sort
	 */
	public ComparatorChain(Comparator<? super T> comparator, boolean reverse) {
		chain = new ArrayList<Comparator<? super T>>();
		chain.add(comparator);
		orderingBits = new BitSet(1);
		if (reverse) {
			orderingBits.set(0);
		}
	}

	public ComparatorChain(Comparator<? super T>... comparator) {
		if (comparator.length != 0) {
			//注意!!!这里之所以再包一个ArrayList,是因为Arrays.asList方法返回的list实例是不可变长的!add会出错
			chain = new ArrayList<Comparator<? super T>>(Arrays.asList(comparator));
			orderingBits = new BitSet(chain.size());
		} else {
			chain = new ArrayList<Comparator<? super T>>();
			orderingBits = new BitSet();
		}
	}

	/**
	 * Construct a ComparatorChain from the Comparators in the List. All
	 * Comparators will default to the forward sort order.
	 * 
	 * @param list List of Comparators
	 * @see #ComparatorChain(List,BitSet)
	 */
	public ComparatorChain(List<Comparator<? super T>> list) {
		this(list, new BitSet(list.size()));
	}

	/**
	 * Construct a ComparatorChain from the Comparators in the given List.
	 * The sort order of each column will be drawn from the given BitSet.
	 * When determining the sort order for Comparator at index
	 * <i>i</i> in the List, the ComparatorChain will call
	 * BitSet.get(<i>i</i>). If that method returns <i>false</i>, the
	 * forward sort order is used; a return value of <i>true</i> indicates
	 * reverse
	 * sort order.
	 * 
	 * @param list List of Comparators. NOTE: This constructor does not
	 * perform a defensive copy of the list
	 * @param bits Sort order for each Comparator. Extra bits are ignored,
	 * unless extra Comparators are added by another method.
	 */
	public ComparatorChain(List<Comparator<? super T>> list, BitSet bits) {
		chain = list;
		orderingBits = bits;
	}

	//-----------------------------------------------------------------------
	public ComparatorChain<T> addComparators(Comparator<? super T>... otherComparator) {
		for (final Comparator<? super T> comparator : otherComparator) {
			addComparator(comparator, false);
		}
		return this;
	}

	/**
	 * Add a Comparator to the end of the chain using the forward sort
	 * order
	 * 
	 * @param comparator Comparator with the forward sort order
	 */
	public ComparatorChain<T> addComparator(Comparator<? super T> comparator) {
		addComparator(comparator, false);
		return this;
	}

	/**
	 * Add a Comparator to the end of the chain using the given sort order
	 * 
	 * @param comparator Comparator to add to the end of the chain
	 * @param reverse false = forward sort order; true = reverse sort order
	 */
	public ComparatorChain<T> addComparator(Comparator<? super T> comparator, boolean reverse) {
		checkLocked();

		chain.add(comparator);
		if (reverse) {
			orderingBits.set(chain.size() - 1);
		}
		return this;
	}

	/**
	 * Replace the Comparator at the given index, maintaining the existing
	 * sort order.
	 * 
	 * @param index index of the Comparator to replace
	 * @param comparator Comparator to place at the given index
	 * @exception IndexOutOfBoundsException if index &lt; 0 or index &gt;=
	 * size()
	 */
	public ComparatorChain<T> setComparator(int index, Comparator<? super T> comparator) throws IndexOutOfBoundsException {
		setComparator(index, comparator, false);
		return this;
	}

	/**
	 * Replace the Comparator at the given index in the ComparatorChain,
	 * using the given sort order
	 * 
	 * @param index index of the Comparator to replace
	 * @param comparator Comparator to set
	 * @param reverse false = forward sort order; true = reverse sort order
	 */
	public ComparatorChain<T> setComparator(int index, Comparator<? super T> comparator, boolean reverse) {
		checkLocked();

		chain.set(index, comparator);
		if (reverse) {
			orderingBits.set(index);
		} else {
			orderingBits.clear(index);
		}
		return this;
	}

	/**
	 * Change the sort order at the given index in the ComparatorChain to a
	 * forward sort.
	 * 
	 * @param index Index of the ComparatorChain
	 */
	public ComparatorChain<T> setForwardSort(int index) {
		checkLocked();
		orderingBits.clear(index);
		return this;
	}

	/**
	 * Change the sort order at the given index in the ComparatorChain to a
	 * reverse sort.
	 * 
	 * @param index Index of the ComparatorChain
	 */
	public ComparatorChain<T> setReverseSort(int index) {
		checkLocked();
		orderingBits.set(index);
		return this;
	}

	/**
	 * Number of Comparators in the current ComparatorChain.
	 * 
	 * @return Comparator count
	 */
	public int size() {
		return chain.size();
	}

	/**
	 * Determine if modifications can still be made to the ComparatorChain.
	 * ComparatorChains cannot be modified once they have performed a
	 * comparison.
	 * 
	 * @return true = ComparatorChain cannot be modified; false =
	 * ComparatorChain can still be modified.
	 */
	public boolean isLocked() {
		return isLocked;
	}

	// throw an exception if the ComparatorChain is locked
	private void checkLocked() {
		if (isLocked) {
			throw new UnsupportedOperationException("Comparator ordering cannot be changed after the first comparison is performed");
		}
	}

	private void checkChainIntegrity() {
		if (chain.size() == 0) {
			throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator");
		}
	}

	//-----------------------------------------------------------------------
	/**
	 * 按照比较器链的顺序比较两个对象,快速比较法(本词意思参考"快速失败":取第一个比较结果不为0的比较器的结果).
	 * 因此比较器的顺序会影响比较结果
	 * 
	 * @param o1 the first object to compare
	 * @param o2 the second object to compare
	 * @return -1, 0, or 1
	 * @exception UnsupportedOperationException if the ComparatorChain does
	 * not contain at least one Comparator
	 */
	public int compare(T o1, T o2) throws UnsupportedOperationException {
		if (!isLocked) {
			checkChainIntegrity();
			isLocked = true;
		}
		// iterate over all comparators in the chain
		int comparatorIndex = 0;
		for (final Comparator<? super T> comparator : chain) {
			int retval = comparator.compare(o1, o2);
			if (retval != 0) {
				// invert the order if it is a reverse sort
				if (orderingBits.get(comparatorIndex) == true) {
					if (Integer.MIN_VALUE == retval) {
						retval = Integer.MAX_VALUE;
					} else {
						retval *= -1;
					}
				}
				return retval;
			}
			++comparatorIndex;
		}
		// if comparators are exhausted, return 0
		return 0;
	}

	//-----------------------------------------------------------------------
	/**
	 * Implement a hash code for this comparator that is consistent with {@link #equals(Object) equals}.
	 * 
	 * @return a suitable hash code
	 * @since Commons Collections 3.0
	 */
	@Override
	public int hashCode() {
		int hash = 0;
		if (null != chain) {
			hash ^= chain.hashCode();
		}
		if (null != orderingBits) {
			hash ^= orderingBits.hashCode();
		}
		return hash;
	}

	/**
	 * Returns <code>true</code> if <i>that</i> Object is is a {@link Comparator} whose ordering is known to be equivalent to mine.
	 * <p>
	 * This implementation returns <code>true</code> if <code><i>object</i>.{@link Object#getClass() getClass()}</code> equals <code>this.getClass()</code>, and the underlying comparators and order bits are equal. Subclasses may want to override this behaviour to remain consistent with the {@link Comparator#equals(Object)} contract.
	 * 
	 * @param object the object to compare with
	 * @return true if equal
	 * @since Commons Collections 3.0
	 */
	@Override
	@SuppressWarnings("unchecked")
	public boolean equals(Object object) {
		if (this == object) {
			return true;
		} else if (null == object) {
			return false;
		} else if (object.getClass().equals(this.getClass())) {
			final ComparatorChain<T> other = (ComparatorChain<T>) object;
			return ((null == orderingBits ? null == other.orderingBits : orderingBits.equals(other.orderingBits)) && (null == chain ? null == other.chain
					: chain.equals(other.chain)));
		} else {
			return false;
		}
	}

}
